/*
 * Implementacion de Simbolo para la Tabla de Simbolos para el lenguaje C Minus.
 * 
 * Basado en el proyecto descrito en: 
 * Louden, K. (1997). Compiler Construction: Principles and Practice. Boston: PWS.
 * 
 * @ Project: Compiler
 * @ File Name: Analyzer.java
 */
package cml.analyzing;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.ListIterator;

import cml.TokenType;
import cml.Type;
import cml.parsing.tree.*;

public class Analyzer {
	
	private SymTable currentTable;
	private ArrayList<SymTable> tables;
	private boolean funcHasReturned;
	private boolean trace;
	private LinkedHashMap<Integer, ArrayList<String>> semErr;
	
	public static final int GLOBAL_SCOPE = 0;
	public static final int FUNC_SCOPE = 1;
	
	/*
	 * Constructo de la clase.
	 */
	public Analyzer() {
		
		this.tables = new ArrayList<SymTable>();
		this.semErr = new LinkedHashMap<Integer, ArrayList<String>>();
		this.funcHasReturned = false;
	}
	
	/*
	 * Busca un simbolo de variable por nombre.
	 * 
	 * @param	name			nombre del simbolo
	 * @param	lookInGlobal	indica si debe buscar en el bloque global
	 */
	private Symbol lookupVarSymbol(String name, boolean lookInGlobal) {
		
		ListIterator<SymTable> lit = this.tables.listIterator(this.tables.indexOf(this.currentTable));
		
		SymTable table = this.currentTable;
		
		do {
			
			if(table.isActive()) {
				
				Symbol sym = table.getSymbol(name);
				
				if(sym != null)
					return sym;
			}
			
			if(lit.hasPrevious())
				table = lit.previous();
			else lookInGlobal = false;
		}
		while(lit.hasPrevious() || lookInGlobal);
		
		return null;
	}
	
	/*
	 * Busca un simbolo de funcion por nombre.
	 * 
	 * @param	name		nombre de la funcion
	 */
	private FuncSymbol lookupFuncSymbol(String name) {
		
		SymTable table = this.tables.get(GLOBAL_SCOPE);
		FuncSymbol sym = (FuncSymbol)table.getSymbol(name);
		
		if(sym != null)
			return sym;
		else return null;
	}
	
	/*
	 * Indica si la lista de tipos de dato de parametros a y b son iguales.
	 * 
	 * @return	<code>true</code> si son iguales; en caso contrario no
	 */
	private boolean equalParamsType(ArrayList<Type> a, ArrayList<Type> b) {
		
		if(a == null && b == null)
			return true;
		
		if((a == null && b != null) || (a != null && b == null))
			return false;
		
		if(a.size() != b.size())
			return false;
		
		ListIterator<Type> lit = a.listIterator();
		
		while(lit.hasNext())
			if(b.get(lit.nextIndex()) != lit.next())
				return false;
		
		return true;
	}
	
	/*
	 * Regresa un texto de los tipos de dato de los parametros de la funcion
	 * 
	 * @parama	ArrayList	lista con los tipos de dato
	 * @return	el texto de la firma de la funcion
	 */
	public String getFuncSignatureString(ArrayList<Type> paramsType) {
		
		String signature = "(";
		
		if(paramsType != null) {
			
			ListIterator<Type> lit = paramsType.listIterator();
			
			signature += lit.next();
			
			while(lit.hasNext())
				signature += "," + lit.next();
		}
		
		signature += ")";
		
		return signature;
	}
	
	/*
	 * Inserta un nodo como simbolo en la Tabla de Simbolos.
	 * 
	 * @param	node			nodo a insertar
	 */
	private void insertSymbol(SynNode node, boolean insert) {
		
		while(node != null) {
			
			SymTable previousTable = null;
			
			if(node instanceof VarDeclNode && insert) {
				
				VarDeclNode temp = (VarDeclNode)node;
				
				if(this.lookupVarSymbol(temp.getName(), false) == null) {
					
					TypeNode type = (TypeNode)temp.getChild(temp.TYPE);
					
					Integer value;
					
					if(temp.getChildCount() == 2) {
						
						NumNode num = (NumNode)temp.getChild(temp.SIZE);
						value = (Integer)num.getValue();
					}
					else value = new Integer(1);
					
					if(type.getType() != Type.VOID)
						if(value.intValue() > 0)
							this.currentTable.addSymbol(new Symbol(temp));
						else this.putError(temp.getLineNo(), "'" +  value.intValue() + "' no es una longitud " +
								"valida para " + "arreglos, variable: '" + temp.getName() + "'");
					else this.putError(temp.getLineNo(), "'vacio' no es un tipo valido para variables: '" + 
										temp.getName() + "'");
				}
				else this.putError(temp.getLineNo(), "Duplicado de variable '" + temp.getName() + "'");	
			}
			else if(node instanceof ParamNode && insert) {
				
				ParamNode temp = (ParamNode)node;
				
				if(this.lookupVarSymbol(temp.getName(), false) == null) {
					
					TypeNode type = (TypeNode)temp.getChild(temp.TYPE);
					
					if(type.getType() != Type.VOID)
						this.currentTable.addSymbol(new Symbol(temp));
					else this.putError(temp.getLineNo(), "'vacio' no es un tipo valido para parametros: '" + 
							temp.getName() + "'");
				}
				else this.putError(temp.getLineNo(), "Duplicado de parametro '" + temp.getName() + "'");
			}
			else if(node instanceof FuncDeclNode) {
				
				FuncDeclNode temp = (FuncDeclNode)node;
				
				FuncSymbol fs = new FuncSymbol(temp);
				
				temp.setName(temp.getName() + this.getFuncSignatureString(fs.getParamsType()));
				
				if(this.lookupFuncSymbol(temp.getName()) == null) {
					
					previousTable = this.currentTable;
					this.currentTable.addSymbol(fs);
					
					SymTable func = new SymTable(this.currentTable.getName() + "." + temp.getName(), FUNC_SCOPE);
					this.tables.add(func);
					this.currentTable = func;
					insert = true;
				}
				else {
					
					this.putError(temp.getLineNo(), "Duplicado de funcion '" + temp.getName() + "'");
					insert = false;
				}
			}
			else if(node instanceof IfNode) {
				
				previousTable = this.currentTable;
				SymTable stmt = new SymTable(this.currentTable.getName() + ".if", 
						this.currentTable.getScopeLevel() + 1);
				
				this.tables.add(stmt);
				this.currentTable = stmt;
			}
			else if(node instanceof ElseNode) {
				
				previousTable = this.currentTable;
				SymTable stmt = new SymTable(this.currentTable.getName() + ".else", 
						this.currentTable.getScopeLevel() + 1);
				
				this.tables.add(stmt);
				this.currentTable = stmt;
			}
			else if(node instanceof ForNode) {
				
				previousTable = this.currentTable;
				SymTable stmt = new SymTable(this.currentTable.getName() + ".for", 
						this.currentTable.getScopeLevel() + 1);
				
				this.tables.add(stmt);
				this.currentTable = stmt;
			}
			else if(node instanceof WhileNode) {
				
				previousTable = this.currentTable;
				SymTable stmt = new SymTable(this.currentTable.getName() + ".while", 
						this.currentTable.getScopeLevel() + 1);
				
				this.tables.add(stmt);
				this.currentTable = stmt;
			}
			
			for(int i = 0; i < node.getChildCount(); i++)
				this.insertSymbol(node.getChild(i), insert);
			
			if(previousTable != null) {
				
				this.currentTable.setActive(false);
				this.currentTable = previousTable;
			}
			
			node = node.getSibling();
		}
	}
	
	/*
	 * Agrega las funciones predefinidas del ambiente de C Minus.
	 */
	private void addEnvFunctions() {
		
		FuncDeclNode func; 
		TypeNode type;
		ParamNode param;
		FuncSymbol fs;
		
		func = new FuncDeclNode("lee");
		type = new TypeNode("entero");
		type.setType(Type.INT);
		func.addChild(type);
		func.addChild(null);
		func.addChild(null);
		
		fs = new FuncSymbol(func);
		func.setName(func.getName() + this.getFuncSignatureString(fs.getParamsType()));
		this.currentTable.addSymbol(fs);
		
		func = new FuncDeclNode("imprime");
		type = new TypeNode("vacio");
		type.setType(Type.VOID);
		func.addChild(type);
		param = new ParamNode("t");
		type = new TypeNode("texto");
		type.setType(Type.TEXT);
		param.addChild(type);
		func.addChild(param);
		func.addChild(null);
		
		fs = new FuncSymbol(func);
		func.setName(func.getName() + this.getFuncSignatureString(fs.getParamsType()));
		this.currentTable.addSymbol(fs);
		
		func = new FuncDeclNode("imprime");
		type = new TypeNode("vacio");
		type.setType(Type.VOID);
		func.addChild(type);
		param = new ParamNode("e");
		type = new TypeNode("entero");
		type.setType(Type.INT);
		param.addChild(type);
		func.addChild(param);
		func.addChild(null);
		
		fs = new FuncSymbol(func);
		func.setName(func.getName() + this.getFuncSignatureString(fs.getParamsType()));
		this.currentTable.addSymbol(fs);
		
		func = new FuncDeclNode("imprime");
		type = new TypeNode("vacio");
		type.setType(Type.VOID);
		func.addChild(type);
		param = new ParamNode("d");
		type = new TypeNode("decimal");
		type.setType(Type.DEC);
		param.addChild(type);
		func.addChild(param);
		func.addChild(null);
		
		fs = new FuncSymbol(func);
		func.setName(func.getName() + this.getFuncSignatureString(fs.getParamsType()));
		this.currentTable.addSymbol(fs);
		
		func = new FuncDeclNode("imprime");
		type = new TypeNode("vacio");
		type.setType(Type.VOID);
		func.addChild(type);
		param = new ParamNode("b");
		type = new TypeNode("booleano");
		type.setType(Type.BOOLEAN);
		param.addChild(type);
		func.addChild(param);
		func.addChild(null);
		
		fs = new FuncSymbol(func);
		func.setName(func.getName() + this.getFuncSignatureString(fs.getParamsType()));
		this.currentTable.addSymbol(fs);
	}
	
	/*
	 * Construye las Tablas de Simbolos a partir del Arbol Sintactico.
	 */
	private void buildSymTables(SynNode tree) {
		
		SymTable global = new SymTable("global", GLOBAL_SCOPE);
		this.tables.add(global);
		this.currentTable = global;
		
		this.addEnvFunctions();
		this.insertSymbol(tree, true);
		
		for(int i = this.tables.size() - 1; i >= 0; i--)
			if(this.tables.get(i).isEmpty())
				this.tables.remove(i);
		
		Symbol principal = this.lookupFuncSymbol("principal" + this.getFuncSignatureString(null));
		
		if(principal == null || principal.getType() != Type.VOID)
			this.putError(0, "Falta declaracion de funcion '" + Type.VOID + " principal () '");
		
		if(this.trace)
			this.printSymTables();
	}
	
	/*
	 * Busca una Tabla de Simbolos por nombre.
	 * 
	 * @return	la tabla
	 */
	private SymTable lookupSymTable(String name) {
		
		ListIterator<SymTable> lit = this.tables.listIterator(this.tables.indexOf(this.currentTable));
		
		SymTable table;
		
		while(lit.hasNext()) {
			
			table = lit.next();
			
			if(table.getName().equals(name))
				return table;
		}
		
		return null;
	}
	
	/*
	 * Regresa el tipo de dato simple acorde al tipo de dato de arreglo.
	 * 
	 * @param	t	tipo de dato a comparar
	 * 
	 * @return	tipo de dato simple
	 */
	private Type typeOfArray(Type t) {
		
		switch(t) {
			
			case ARRAYOFBOOLEAN: return Type.BOOLEAN;
			case ARRAYOFDEC: return Type.DEC;
			case ARRAYOFINT: return Type.INT;
			case ARRAYOFTEXT: return Type.TEXT;
			default: return Type.VOID;
		}
	}
	
	/*
	 * Regresa la lista de tipos de dato de los argumentos de una llamada a funcion.
	 * 
	 * @param	node	el nodo de la llamada a funcion
	 * 
	 * @return	la lista de tipos de dato
	 */
	private ArrayList<Type> getCallArgsType(CallNode node) {
		
		ExpNode args = (ExpNode)node.getChild(node.ARGS);
		
		if(args == null)
			return null;
		
		ArrayList<Type> argsType = new ArrayList<Type>();
		
		while(args != null) {
			
			argsType.add(args.getType());
			
			args = (ExpNode)args.getSibling();
		}
		
		return argsType;
	}
	
	/*
	 * Determina el tipo de dato de un nodo.
	 * 
	 * @param	node	el nodo
	 */
	private void checkType (SynNode node) {
		
		while(node != null) {
			
			SymTable previousTable = null;
			SymTable newTable = null;
			
			if(node instanceof FuncDeclNode) {
				
				FuncDeclNode temp = (FuncDeclNode)node;
				
				newTable = this.lookupSymTable(this.currentTable.getName() + "." + temp.getName());
				
				if(newTable != null) {
					
					String s[] = newTable.getName().split("\\.");
					
					FuncSymbol fs = this.lookupFuncSymbol(s[s.length - 1]);
					TypeNode type = (TypeNode)temp.getChild(temp.TYPE);
					
					if(fs != null && fs.getType() == type.getType()) {
						
						previousTable = this.currentTable;
						newTable.setActive(true);
						this.currentTable = newTable;
					}
				}
			}
			else if(node instanceof IfNode && this.currentTable.getScopeLevel() == FUNC_SCOPE) {
				
				newTable = this.lookupSymTable(this.currentTable.getName() + ".if");
				
				if(newTable != null) {
					
					previousTable = this.currentTable;
					newTable.setActive(true);
					this.currentTable = newTable;
				}
			}
			else if(node instanceof ElseNode && this.currentTable.getScopeLevel() == FUNC_SCOPE) {
				
				newTable = this.lookupSymTable(this.currentTable.getName() + ".else");
				
				if(newTable != null) {
					
					previousTable = this.currentTable;
					newTable.setActive(true);
					this.currentTable = newTable;
				}
			}
			else if(node instanceof ForNode && this.currentTable.getScopeLevel() == FUNC_SCOPE) {
				
				newTable = this.lookupSymTable(this.currentTable.getName() + ".for");
				
				if(newTable != null) {
					
					previousTable = this.currentTable;
					newTable.setActive(true);
					this.currentTable = newTable;
				}
			}
			else if(node instanceof WhileNode && this.currentTable.getScopeLevel() == FUNC_SCOPE) {
				
				newTable = this.lookupSymTable(this.currentTable.getName() + ".while");
				
				if(newTable != null) {
					
					previousTable = this.currentTable;
					newTable.setActive(true);
					this.currentTable = newTable;
				}
			}
			
			for(int i = 0; i < node.getChildCount(); i++)
				this.checkType(node.getChild(i));
			
			if(node instanceof NumNode) {
				
				NumNode temp = (NumNode)node;
				Object value = temp.getValue();
				
				if(value instanceof Integer)
					temp.setType(Type.INT);
				else if(value instanceof Double)
					temp.setType(Type.DEC);
			}
			else if(node instanceof TextNode) {
				
				TextNode temp = (TextNode)node;
				temp.setType(Type.TEXT);
			}
			else if(node instanceof BoolNode) {
				
				BoolNode temp = (BoolNode)node;
				temp.setType(Type.BOOLEAN);
			}
			else if(node instanceof VarNode) {
				
				VarNode temp = (VarNode)node;
				Symbol sym = this.lookupVarSymbol(temp.getName(), true);
				
				if(sym != null) {
					
					ExpNode index = (ExpNode)temp.getChild(temp.INDEX);
					
					if(index != null)
						temp.setType(this.typeOfArray(sym.getType()));
					else temp.setType(sym.getType());
				}
				else
					this.putError(temp.getLineNo(), "Uso de variable '" + temp.getName() + "' no declarada");
			}
			else if(node instanceof OpNode) {
				
				OpNode temp = (OpNode)node;
				String name = temp.getName();
				
				ExpNode c1 = (ExpNode)temp.getChild(temp.LEFT);
				ExpNode c2 = (ExpNode)temp.getChild(temp.RIGHT);
				
				if(name.equals(TokenType.EQ.toString()) || name.equals(TokenType.NEQ.toString()) || 
					name.equals(TokenType.LT.toString()) || name.equals(TokenType.LTEQ.toString()) || 
					name.equals(TokenType.GT.toString()) || name.equals(TokenType.GTEQ.toString()))
					temp.setType(Type.BOOLEAN);
				else if(name.equals(TokenType.PLUS.toString()) || name.equals(TokenType.MINUS.toString()) || 
						name.equals(TokenType.TIMES.toString()) || name.equals(TokenType.OVER.toString())) {
					
					if(c1 != null && c2 != null) {
						
						if((c1.getType() == Type.ARRAYOFINT || c1.getType() == Type.ARRAYOFDEC) &&
							(c2.getType() == Type.ARRAYOFINT || c2.getType() == Type.ARRAYOFDEC))
							this.putError(temp.getLineNo(), "No se puede operar aritmeticamente arreglos");
						else if((c1.getType() == c2.getType()))
							temp.setType(c1.getType());
						else this.putError(temp.getLineNo(), "Operacion aritmetica de tipos no compatibles, " +
										"no se puede convertir de '" + c2.getType() + "' a '" + c1.getType() +
										"'");
					}	
				}
				else if(name.equals(TokenType.ASSIGN.toString())) {
					
					if(c1 != null && c2 != null) {
						
						if(c1.getType() == c2.getType())
							temp.setType(c1.getType());
						else this.putError(temp.getLineNo(), "Asignacion de tipos diferentes, no se puede " +
											"convertir de '" + c2.getType() + "' a '" + c1.getType() + "'");
					}
				}
			}
			else if(node instanceof CallNode) {
				
				CallNode temp = (CallNode)node;
				
				ArrayList<Type> argsType = this.getCallArgsType(temp);
				
				temp.setName(temp.getName() + this.getFuncSignatureString(argsType));
				
				FuncSymbol fs = this.lookupFuncSymbol(temp.getName());
				
				if(fs != null)
					temp.setType(fs.getType());
				else
					this.putError(temp.getLineNo(), "Uso de funcion '" + temp.getName() + "' no declarada");
			}
			
			if(previousTable != null) {
				
				this.currentTable.setActive(false);
				this.currentTable = previousTable;
			}
			
			node = node.getSibling();
		}
	}
	
	/*
	 * Realiza la revision de tipo de dato de los enunciados de regreso de funciones
	 * 
	 * @param	node	el nodo
	 * @param	fs		el simbolo de la funcion
	 */
	private void returnStmtCheck(SynNode node, Type returnType) {
		
		while(node != null) {
			
			if(node instanceof FuncDeclNode) {
				
				FuncDeclNode temp = (FuncDeclNode)node;
				TypeNode type = (TypeNode)temp.getChild(temp.TYPE);
				returnType = type.getType();
				
				this.funcHasReturned = false;
			}
			
			for(int i = 0; i < node.getChildCount(); i++)
				this.returnStmtCheck(node.getChild(i), returnType);
			
			if(node instanceof ReturnNode) {
				
				ReturnNode temp = (ReturnNode)node;
				ExpNode body = (ExpNode)temp.getChild(temp.BODY);
				
				if(returnType == Type.VOID && body != null)
					this.putError(temp.getLineNo(), "Metodos 'vacio' no pueden regresar un valor");
				else if(body != null && !(body.getType() == returnType))
					this.putError(temp.getLineNo(), "Regreso de tipos diferentes, no se puede " +
							"convertir de '" + body.getType() + "' a '" + returnType + "'");
				
				this.funcHasReturned  = true;
				
				if(node.getSibling() != null)
					this.putError(node.getSibling().getLineNo(), "Codigo inalcanzable");
			}
			
			if(node instanceof FuncDeclNode && !this.funcHasReturned && returnType != Type.VOID) {
				
				FuncDeclNode temp = (FuncDeclNode)node;
				
				this.putError(temp.getLineNo(), "La funcion '" + temp.getName() + "' debe regresa un valor de " +
								"tipo " + returnType);
			}
			
			node = node.getSibling();
		}
	}
	
	/*
	 * Realiza la revision de tipos de dato a partir del Arbol Sintactico.
	 * 
	 * @param	tree	el arbol sintactico
	 */
	private void typeChecking(SynNode tree) {
		
		this.checkType(tree);
		this.returnStmtCheck(tree, Type.VOID);
	}
	
	/*
	 * Realiza el Analisis Semantico a partir del Arbol Sintactico.
	 * 
	 * @param	tree	el arbol sintactico
	 */
	public void analyze(SynNode tree) {
		
		this.buildSymTables(tree);
		this.typeChecking(tree);
		
		ArrayList<Integer> keys = new ArrayList<Integer>(this.semErr.keySet());
		Collections.sort(keys);
		
		LinkedHashMap<Integer, ArrayList<String>> sortedSemErr = new LinkedHashMap<Integer, ArrayList<String>>();
		
		for(ListIterator<Integer> lit = keys.listIterator(); lit.hasNext();) {
			
			Integer key = lit.next();
			
			sortedSemErr.put(key, this.semErr.get(key));
		}
		
		this.semErr = sortedSemErr;
		
		for(Iterator<Integer> it = this.semErr.keySet().iterator(); it.hasNext() && trace;) {
			
			Integer key = it.next();
			
			for(String err : this.semErr.get(key))
				this.traceError(key.intValue(), err);
		}
				
	}
	
	/*
	 * Regresa la lista de las Tablas de Simbolos.
	 * 
	 * @return	la lista de tablas
	 */
	public ArrayList<SymTable> getTables() {
		
		return this.tables;
	}
	
	/*
	 * Regresa la lista de errores semanticos.
	 * 
	 * @return	un mapa con los errores y los numeros de linea
	 */
	public LinkedHashMap<Integer, ArrayList<String>> getSemErr() {
		
		return this.semErr;
	}
	
	/*
	 * Habilita/deshabilita el mostrar en consola un reporte de los 
	 * <code>tokens</code> encontrados.
	 * 
	 * @param	boolean	si <code>true</code>, muestra el reporte; en caso contrario no lo hace
	 */
	public void setTrace(boolean t) {
		
		this.trace = t;
	}
	
	/*
	 * Imprime las Tablas de Simbolos.
	 */
	private void printSymTables() {
		
		for(SymTable table : this.tables) {
			
			SymTable.printTable(table);
			System.out.println();
		}
	}
	
	/*
	 * Agrega un error semantico y su numero de linea a la lista de errores.
	 * 
	 * @param	int	el numero de linea
	 * @param	err	el error
	 */
	private void putError(int lineNo, String err) {
		
		ArrayList<String> errList = this.semErr.get(lineNo);
		
		if(errList == null) {
			
			errList = new ArrayList<String>();
			errList.add(err);
			this.semErr.put(lineNo, errList);
		}
		else this.semErr.get(lineNo).add(err);
	}
	
	/*
	 * Imprime el error semantico y su numero de linea.
	 * 
	 * @param	err	el error
	 * @param	int	el numero de linea
	 */
	private void traceError(int lineNo, String err) {
		
		if(err != null)
			System.err.println((lineNo + 1) + "| Error semantico: " + err);
	}
}
